home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / docme.lha / doc.me / prepro.me < prev    next >
Text File  |  1992-09-25  |  43KB  |  1,604 lines
  1. .\" use: pic | tbl | eqn | ditroff -me
  2. .\"
  3. .\"    "@(#)bibmac.me    2.2    9/9/83";
  4. .de IP
  5. .ip \\$1 \\$2
  6. ..
  7. .de LP
  8. .lp
  9. ..
  10. .\"    @(#)bmac.std    2.2    9/9/83;
  11. .\" standard format troff commands
  12. .\" citation formatting strings
  13. .ds [[ [
  14. .ds ]] ]
  15. .ds ], ,\|
  16. .ds ]- -
  17. .ds [. " \&
  18. .ds .] .
  19. .ds [, " \&
  20. .ds ,] ,
  21. .ds [? " \&
  22. .ds ?] ?
  23. .ds [: " \&
  24. .ds :] :
  25. .ds [; " \&
  26. .ds ;] ;
  27. .ds [! " \&
  28. .ds !] !
  29. .ds [" " \&
  30. .ds "] \&"
  31. .ds [' " \&
  32. .ds '] '
  33. .ds [< " \&
  34. .ds >]
  35. .\" reference formmating strings
  36. .ds a] " \&
  37. .ds b] , \&
  38. .ds c] , \&
  39. .ds n] "\& and \&
  40. .ds m] "\& and \&
  41. .ds p] .
  42. .\" reference formmating macros
  43. .de s[   \" start reference
  44. .nh
  45. .IP [\\*([F] 5m
  46. ..
  47. .de e[   \" end reference
  48. .[-
  49. ..
  50. .de []   \" start to display collected references
  51. .LP
  52. ..
  53. .de ][   \" choose format
  54. .ie !"\\*([J"" \{\
  55. .    ie !"\\*([V"" .nr t[ 1    \" journal
  56. .    el            .nr t[ 5    \" conference paper
  57. .\}
  58. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  59. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  60. .el .ie !"\\*([I"" .nr t[ 2    \" book
  61. .el                .nr t[ 0    \" other
  62. .\\n(t[[
  63. ..
  64. .de 0[   \" other
  65. .s[
  66. .if !"\\*([A"" \\*([A\\c
  67. .if !"\\*([T"" , \\*([T\\c
  68. .if !"\\*([V"" , Vol. \\*([V\\c
  69. .if !"\\*([O"" , \\*([O\\c
  70. .if !"\\*([D"" , \\*([D\\c
  71. \&.
  72. .e[
  73. ..
  74. .de 1[ \" journal article
  75. .s[
  76. .if !"\\*([A"" \\*([A,
  77. .if !"\\*([T""  \\*([T,
  78. \\fI\\*([J \\*([V\\fP\c
  79. .if !"\\*([N"" ,\\*([N
  80. .if !"\\*([D"" (\\*([D)\c
  81. .if !"\\*([P"" , \\*([P\c
  82. .if !"\\*([I"" , \\*([I\c
  83. \\&.
  84. .if !"\\*([O"" \\*([O.
  85. .e[
  86. ..
  87. .de 2[ \" book
  88. .s[
  89. .ie !"\\*([A"" \\*([A,
  90. .el .if !"\\*([E"" \{\
  91. .       ie \\n([E-1 \\*([E, eds.,
  92. .       el \\*([E, ed.,\}
  93. .if !"\\*([T"" \\fI\\*([T\\fP,
  94. .rm a[
  95. .if !"\\*([I"" .ds a[ \\*([I
  96. .if !"\\*([C"" \{\
  97. .       if !"\\*(a["" .as a[ , \\&
  98. .       as a[ \\*([C\}
  99. .if !"\\*([D"" \{\
  100. .       if !"\\*(a["" .as a[ , \\&
  101. .       as a[ \\*([D\}
  102. \\*(a[.
  103. .if !"\\*([G"" Gov. ordering no. \\*([G.
  104. .if !"\\*([O"" \\*([O.
  105. .e[
  106. ..
  107. .de 3[ \" article in book
  108. .s[
  109. .if !"\\*([A"" \\*([A,
  110. .if !"\\*([T"" \\*([T,
  111. in \\fI\\*([B\\fP\c
  112. .if !"\\*([V"" , vol. \\*([V
  113. .if !~\\*([E~~ \{\
  114. .       ie , \\n([E-1  \\*([E (editors)\c
  115. .       el , \\*([E (editor)\c\}
  116. .if !"\\*([I"" , \\*([I\c
  117. .if !"\\*([C"" , \\*([C\c
  118. .if !"\\*([D"" , \\*([D\c
  119. .if !"\\*([P"" , \\*([P\c
  120. \\&.
  121. .if !"\\*([O"" \\*([O.
  122. .e[
  123. ..
  124. .de 4[ \" report
  125. .s[
  126. .if !"\\*([A"" \\*([A,
  127. .if !~\\*([E~~ \{\
  128. .       ie \\n([E-1 \\*([E, editors.
  129. .       el \\*([E, editor.\}
  130. \\*([T,
  131. \\*([R\c
  132. .if !"\\*([G"" \& (\\*([G)\c
  133. .if !"\\*([I"" , \\*([I\c
  134. .if !"\\*([C"" , \\*([C\c
  135. .if !"\\*([D"" , \\*([D\c
  136. \\&.
  137. .if !"\\*([O"" \\*([O.
  138. .e[
  139. ..
  140. .de 5[ \" conference paper
  141. .s[
  142. .if !"\\*([A"" \\*([A,
  143. .if !"\\*([T"" \\*([T,
  144. \\fI\\*([J\\fP,
  145. .if !"\\*([C"" \\*([C,
  146. .if !"\\*([D"" \\*([D\c
  147. .if !"\\*([P"" , \\*([P\c
  148. \\&.
  149. .if !"\\*([O"" \\*([O.
  150. .e[
  151. ..
  152. .de [-   \" clean up after yourself
  153. .rm [A [B [C [D
  154. .rm [E [F [G
  155. .rm [I [J [K
  156. .rm [N [O [P
  157. .rm [R [T
  158. .rm [V [W
  159. ..
  160. .\"    @(#)bmac.std    2.2    8/24/83;
  161. .\" standard format troff commands
  162. .\" citation formatting strings
  163. .ds [[ [
  164. .ds ]] ]
  165. .ds ], ,\|
  166. .ds ]- -
  167. .ds [. " \&
  168. .ds .] .
  169. .ds [, " \&
  170. .ds ,] ,
  171. .ds [< " \&
  172. .ds >]
  173. .\" reference formmating strings
  174. .ds c] , \&
  175. .ds n] "" and \&
  176. .ds m] "" and \&
  177. .ds a] " \&
  178. .\" reference formmating macros
  179. .de s[   \" start reference
  180. .nh
  181. .IP [\\*([F] 5m
  182. ..
  183. .de e[   \" end reference
  184. .[-
  185. ..
  186. .de []   \" start to display collected references
  187. .SH
  188. References
  189. .LP
  190. ..
  191. .de ][   \" choose format
  192. .ie !"\\*([J"" \{\
  193. .    ie !"\\*([V"" .nr t[ 1    \" journal
  194. .    el            .nr t[ 5    \" conference paper
  195. .\}
  196. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  197. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  198. .el .ie !"\\*([I"" .nr t[ 2    \" book
  199. .el                .nr t[ 0    \" other
  200. .\\n(t[[
  201. ..
  202. .de 0[   \" other
  203. .s[
  204. .if !"\\*([A"" \\*([A,
  205. .if !"\\*([T"" \\*([T,
  206. .if !"\\*([O"" \\*([O\c
  207. .if !"\\*([D"" , \\*([D\c
  208. \&.
  209. .e[
  210. ..
  211. .de 1[ \" journal article
  212. .s[
  213. .if !"\\*([A"" \\*([A,
  214. .if !"\\*([T"" \\*([T,
  215. \\fI\\*([J \\*([V\\fP,
  216. .if !"\\*([N"" \\*([N
  217. .if !"\\*([D"" (\\*([D),
  218. .if !"\\*([P"" \\*([P\c
  219. .if !"\\*([I"" , \\*([I\c
  220. \\&.
  221. .if !"\\*([O"" \\*([O.
  222. .e[
  223. ..
  224. .de 2[ \" book
  225. .s[
  226. .ie !"\\*([A"" \\*([A,
  227. .el .if !"\\*([E"" \{\
  228. .       ie \\n([E-1 \\*([E, eds.,
  229. .       el \\*([E, ed.,\}
  230. .if !"\\*([T"" \\fI\\*([T\\fP,
  231. .rm a[
  232. .if !"\\*([I"" .ds a[ \\*([I
  233. .if !"\\*([C"" \{\
  234. .       if !"\\*(a["" .as a[ , \\&
  235. .       as a[ \\*([C\}
  236. .if !"\\*([D"" \{\
  237. .       if !"\\*(a["" .as a[ , \\&
  238. .       as a[ \\*([D\}
  239. \\*(a[.
  240. .if !"\\*([G"" Gov. ordering no. \\*([G.
  241. .if !"\\*([O"" \\*([O.
  242. .e[
  243. ..
  244. .de 3[ \" article in book
  245. .s[
  246. .if !"\\*([A"" \\*([A,
  247. .if !"\\*([T"" \\*([T,
  248. in \\fI\\*([B\\fP,
  249. .if !"\\*([V"" vol. \\*([V,
  250. .if !"\\*([E"" \\*([E (ed.),
  251. .if !"\\*([I"" \\*([I,
  252. .if !"\\*([C"" \\*([C,
  253. .if !"\\*([D"" \\*([D\c
  254. .if !"\\*([P"" , \\*([P\c
  255. \\&.
  256. .if !"\\*([O"" \\*([O.
  257. .e[
  258. ..
  259. .de 4[ \" report
  260. .s[
  261. .if !"\\*([A"" \\*([A,
  262. \\*([T,
  263. \\*([R\c
  264. .if !"\\*([G"" \& (\\*([G)\c
  265. .if !"\\*([I"" , \\*([I\c
  266. .if !"\\*([C"" , \\*([C\c
  267. .if !"\\*([D"" , \\*([D\c
  268. \\&.
  269. .if !"\\*([O"" , \\*([O.
  270. .e[
  271. ..
  272. .de 5[ \" conference paper
  273. .s[
  274. .if !"\\*([A"" \\*([A,
  275. .if !"\\*([T"" \\*([T,
  276. \\fI\\*([J\\fP,
  277. .if !"\\*([C"" \\*([C\c
  278. .if !"\\*([D"" , \\*([D\c
  279. .if !"\\*([P"" , \\*([P\c
  280. \\&.
  281. .if !"\\*([O"" , \\*([O.
  282. .e[
  283. ..
  284. .de [-   \" clean up after yourself
  285. .rm [A [B [C [D
  286. .rm [E [F [G
  287. .rm [I [J [K
  288. .rm [N [O [P
  289. .rm [R [T
  290. .rm [V [W
  291. ..
  292. .if t \{ \
  293. .pl 29.7c    \" page length
  294. .po 2.5c    \" page offset (left margin)
  295. .ll 16.5c    \" line length
  296. .lt 16.5c    \" title length
  297. .nr LL 16.5c
  298. .nr )l 29.7c
  299. .nr hm 2c
  300. .nr $r 9    \" factor for vertical spacing
  301. .nr $R \n($r
  302. .sz 12        \" font size
  303. .nr pp 12
  304. .nr sp 12
  305. .nr tp 12
  306. .nr fp 10
  307. .hc ~        \" hyphenation character
  308. .        \" Umlauts and sharp s
  309. .ds A \(A:
  310. .ds O \(O:
  311. .ds U \(U:
  312. .ds a \(a:
  313. .ds o \(o:
  314. .ds u \(u:
  315. .ds s \(ss
  316. .        \"  UMLAUT  \*:u, etc.
  317. .ds : \v'-0.6m'\h'(1u-(\\n(.fu%2u))*0.13m+0.06m'\z.\h'0.2m'\z.\h'-((1u-(\\n(.fu%2u))*0.13m+0.26m)'\v'0.6m'
  318. .\}
  319. .if n \{ \
  320. .po 0        \" page offset (left margin)
  321. .ll 78        \" line length
  322. .lt 78        \" title length
  323. .nr $r 4    \" factor for vertical spacing
  324. .nr $R \n($r
  325. .hc ~        \" hyphenation character
  326. .        \" Umlaute und scharfes s
  327. .ds A Ae
  328. .ds O Oe
  329. .ds U Ue
  330. .ds a ae
  331. .ds o oe
  332. .ds u ue
  333. .ds s sz
  334. .\}
  335. .de _
  336. \&\\$1\l'|0\(ul'\\$2
  337. ..
  338. .de FT        \" font for programs
  339. .ft C
  340. .sz -2
  341. ..
  342. .de FR
  343. .ft R
  344. .sz +2
  345. ..
  346. .de []        \" start to display collected references
  347. .uh References
  348. .lp
  349. ..
  350. .de $0        \" collect table of contents
  351. .(x
  352. .ta 2c
  353. .ie '\\$2''    \\$1
  354. .el \\$2.    \\$1
  355. .)x
  356. ..
  357. .de np
  358. .nr $p +1
  359. .ip \\n($p.
  360. ..
  361. .de SH
  362. .sp 0.5
  363. .in -3
  364. .r \\$1
  365. .sp 0.5
  366. .in +3
  367. ..
  368. .de PP
  369. .sp 0.5
  370. ..
  371. .de IP
  372. .ip \\$1 \\$2
  373. ..
  374. .de I
  375. .i \\$1
  376. ..
  377. .de TH
  378. ..
  379. .EQ
  380. delim off
  381. .EN
  382. .hc ~
  383. .ds ], , 
  384. .b " "
  385. .sp 1c
  386. .ta 9c
  387. .ft R
  388. .sz 12
  389. \l'17.1c'
  390. .nf
  391.  
  392.  
  393.     Preprocessors
  394.  
  395.  
  396.     J. Grosch
  397.  
  398.  
  399. \l'17.1c'
  400. .sp 12.5c
  401. \l'17.1c'
  402. .ft H
  403. .nf
  404.     GESELLSCHAFT F\*UR MATHEMATIK
  405.     UND DATENVERARBEITUNG MBH
  406.  
  407.     FORSCHUNGSSTELLE F\*UR
  408.     PROGRAMMSTRUKTUREN
  409.     AN DER UNIVERSIT\*AT KARLSRUHE
  410. .r
  411. \l'17.1c'
  412. .bp
  413. .oh '''%'
  414. .eh '''%'
  415. .ce 99
  416. .sz 20
  417. .b " "
  418. .sp 2
  419. Project
  420. .sp
  421. .b "Compiler Generation"
  422. .sp
  423. .sz 12
  424. \l'15c'
  425. .sp
  426. .sz 16
  427. .b "Preprocessors"
  428. .sp 2
  429. Josef Grosch
  430. .sp 2
  431. .sz 14
  432. Aug. 4, 1992
  433. .sp
  434. .sz 12
  435. \l'15c'
  436. .sp 2
  437. Report No. 24
  438. .sp 2
  439. Copyright \(co 1992 GMD
  440. .sp 2
  441. Gesellschaft f\*ur Mathematik und Datenverarbeitung mbH
  442. Forschungsstelle an der Universit\*at Karlsruhe
  443. Vincenz-Prie\*snitz-Str. 1
  444. D-7500 Karlsruhe
  445. .ce 0
  446. .fi
  447. .bp 1
  448. .ce 99
  449. .b "Preprocessors"
  450. .\" .sp 2
  451. .\" Josef Grosch
  452. .\" GMD Forschungsstelle an der Universit\*at Karlsruhe
  453. .\" Vincenz-Prie\*snitz-Str. 1, D-7500 Karlsruhe, Germany
  454. .\" grosch@karlsruhe.gmd.de
  455. .ce 0
  456. .sp
  457. .sh 1 Introduction
  458. .lp
  459. This manual describes the features and the usage of two kinds of preprocessors contained in
  460. the Karlsruhe Toolbox for Compiler Construction. The preprocessors
  461. .i "cg -xz"
  462. and
  463. .i rpp
  464. derive a parser specification and most of a scanner specification from an attribute grammar.
  465. The preprocessors
  466. .i l2r ,
  467. .i y2l ,
  468. and
  469. .i r2l
  470. convert input for
  471. .i lex
  472. and
  473. .i yacc
  474. into specifications for
  475. .i rex
  476. and
  477. .i lalr
  478. and vice versa. All preprocessors work as filter programs reading input from
  479. .i "standard input"
  480. and writing output to
  481. .i "standard output" .
  482. Some preprocessors can read from a file specified as argument, too.
  483. .sh 1 "Specification of Scanner and Parser with an Attribute Grammar"
  484. .pp
  485. Writing specifications for the scanner generator
  486. .i rex
  487. \*([[Gro87\*(]] and the parser generator
  488. .i lalr
  489. \*([[GrV88\*(]] directly in the tool specific language is a practicable method.
  490. However, it has some disadvantages. Most of the tokens are specified twice and their
  491. internal representation or code, respectively, has to be selected and kept consistent,
  492. manually. Access to
  493. attributes using the yacc-style $i construct (see e.g.\*([<\*([[GrV88\*(]]\*(>]) is less readable
  494. and error-prone in case of changes. The following solution avoids these disadvantages.
  495. .pp
  496. Instead of using the tool specific language for
  497. .i rex
  498. and
  499. .i lalr
  500. directly, a language of higher level is used. It replaces the $i construct by named
  501. attributes and describes a complete parser and most of a scanner in one document.
  502. Two preprocessors transform such a specification into the languages directly understood by
  503. .i rex
  504. and
  505. .i lalr .
  506. Fig. 1 shows the data flow using arrows between boxes and circles.
  507. Boxes represent files or file types and circles represent tools or preprocessors.
  508. The intermediate file named
  509. .i Scanner.rpp
  510. by default
  511. contains the part of the scanner specification that can be extracted from the parser
  512. specification. Table 1 gives the meaning of the file types used in Fig. 1 and this manual.
  513. .(z L
  514. .sp 0.5
  515. .PS
  516. scale    = 2.54
  517. boxwid    = 2.0
  518. boxht    = 1.2
  519. circlerad = 0.6
  520. linewid    = 1.2
  521. lineht    = 1.2
  522. movewid    = 1.2
  523. moveht    = 1.2
  524.  
  525.     down
  526. O:    box ".scan"
  527.     arrow
  528. Rp:    circle "rpp"
  529.     arrow
  530.     box ".rex"
  531.     arrow 
  532. R:    circle "rex"
  533.     move down
  534. D0:    box invis width 3.0
  535. So:    box "Source" at D0.w
  536. Sc:    box "Scanner" at D0.e
  537.     arrow from R.sw to So.n
  538.     arrow from R.se to Sc.n
  539.     move to So.w - (2.75, 0)
  540.  
  541.     down
  542.     box ".pars" at O.c + (6, 0)
  543.     arrow
  544. Cg:    circle "cg -xz"
  545.     arrow
  546.     box ".lalr"
  547.     arrow 
  548. L:    circle "lalr"
  549.     move down
  550. D1:    box invis width 3.0
  551. Pa:    box "Parser" at D1.w
  552. Er:    box "Errors" at D1.e
  553.     arrow from L.sw to Pa.n
  554.     arrow from L.se to Er.n
  555.  
  556.     arrow from Cg.w left 1.4
  557.     box "Scanner" ".rpp"
  558.     arrow to Rp.e
  559. .PE
  560. .sp
  561. .ce
  562. Fig. 1: Data flow during scanner and parser generation
  563. .)z
  564. .(b L
  565. .sp 0.5
  566. .ce
  567. Table 1: Meaning of file types
  568. .sp 0.5
  569. .TS
  570. center box;
  571. l | l.
  572. file type    meaning
  573. _
  574. \&.pars    scanner and parser specification (including S-attribution)
  575. \&.scan    rest of scanner specification
  576. \&.rpp    intermediate data for completion of scanner in .scan
  577. \&.rex    scanner specification understood by \fIrex\fP
  578. \&.lalr    parser specification understood by \fIlalr\fP
  579. \&.ell    input for \fIell\fP (= input for \fPlalr\fP with EBNF constructs\*([<\*([[GrV88\*(]]\*(>])
  580. \&.lex    input for \fIlex\fP
  581. \&.yacc    input for \fIyacc\fP
  582. Source    generated module (or linked from library \fIreuse\fP)
  583. Scanner    generated module
  584. Parser    generated module
  585. Errors    generated module (or linked from library \fIreuse\fP)
  586. .TE
  587. .)b
  588. .pp
  589. The formalism used to describe parsers (.pars) is an extension of the input language
  590. for the tools
  591. .i ast
  592. \*([[Gro91\*(]] and
  593. .i ag
  594. \*([[Gro89\*(]] (see section 2.1.). This leads to a rather uniform set of input languages
  595. for most of the tools and simplifies their use. The preprocessor
  596. .i "cg -xz"
  597. transforms a parser specification in
  598. .i ag
  599. notation into one in
  600. .i lalr
  601. notation and extracts most of a scanner specification. The parser specification in
  602. .i lalr
  603. notation is written on a file named <Parser>.lalr. <Parser> is substituted by the name of
  604. the parser module which defaults to
  605. .i Parser .
  606. The extracted scanner specification is written to a file named <Scanner>.rpp.
  607. <Scanner> is substituted by the name of the scanner module which defaults to
  608. .i Scanner .
  609. The rest of the scanner specification must be written in
  610. the language directly understood by
  611. .i rex .
  612. It has to contain the part of a scanner specification that can not be derived automatically.
  613. This part is usually rather small and comprises the description of user-defined tokens like
  614. identifiers and numbers, comments, and the computation of attributes for the tokens. A few
  615. insertion points are marked to tell the preprocessor
  616. .i rpp
  617. where to include the generated parts (see section 2.2.).
  618. .sh 2 "Parser Specification"
  619. .pp
  620. The input language of
  621. .i ast
  622. and
  623. .i ag
  624. can be used to generate a parser. The details of this language can
  625. be found in the manuals for these tools\*([<\*([[Gro89\*(],Gro91\*(]]\*(>].
  626. The reader should be familiar with these documents because the current manual
  627. describes primarily the extensions necessary for parser generation.
  628. .pp
  629. The language can describe concrete as well as abstract syntaxes. Nonterminal, terminal,
  630. and abstract
  631. symbols or node types are distinguished by the definition characters '=', ':', and ':=',
  632. respectively, and have to be declared by default. However, the option j of
  633. .i "cg -xz"
  634. allows undeclared terminal symbols and declares them implicitly.
  635. In any case, terminal symbols with attributes have to be declared explicitly.
  636. .pp
  637. Note, the following names are reserved for keywords and can not be used for grammar symbols.
  638. Unfortunately, some of them occur frequently as keywords in languages that are being defined.
  639. They should be turned into strings by surrounding apostrophes:
  640. .(b
  641. .FT
  642. BEGIN           CLOSE           DECLARE         DEMAND          END
  643. EVAL            EXPORT          FOR             FUNCTION        GLOBAL
  644. IGNORE          IMPORT          IN              INH             INHERITED
  645. INPUT           LEFT            LOCAL           MODULE          NONE
  646. OUT             OUTPUT          PARSER          PREC            PROPERTY
  647. REMOTE          REV             REVERSE         RIGHT           RULE
  648. SCANNER         SELECT          STACK           SUBUNIT         SYN
  649. SYNTHESIZED     THREAD          TREE            VIEW            VIRTUAL
  650. VOID
  651. .)b
  652. .pp
  653. The right-hand sides of node types without extensions are interpreted as right-hand sides of
  654. grammar rules (see e. g. Assign, Call0, Call, and If in the example below).
  655. The children of the right-hand side form a sequence of terminal and nonterminal symbols
  656. as usual.
  657. The names of those node types serve as rule names.
  658. If a symbol occurs several times on one right-hand side, it has to be preceded by different
  659. selector names (see e. g. the rule named
  660. .i If ).
  661. Attributes in brackets are not interpreted as grammar symbols
  662. but as attribute declarations representing values to be evaluated during parsing.
  663. .pp
  664. Not every name of a node type is interpreted as nonterminal or terminal symbol.
  665. Only those node types that are used (referenced) on some right-hand side and the first node
  666. type which is regarded as start symbol are treated as grammar symbols.
  667. If a node type is defined as nonterminal then
  668. all associated extensions become alternative right-hand sides for this nonterminal symbol.
  669. If a node type is defined as terminal it remains a terminal symbol.
  670. If a node type is not defined and option j is not set an error message is issued.
  671. If option j is set then undefined node types are implicitly defined as terminals.
  672. .pp
  673. The grammar needs not to be reduced. This means it may contain superfluous terminal and
  674. nonterminal symbols. Symbols are superfluous if they are not referenced from any rule.
  675. Those symbols are simply ignored and reported as a warning.
  676. .(b
  677. Example: input of cg -xz
  678. .sp 0.5
  679. .FT
  680. Stat            = <
  681.    Assign       = Adr ':=' Expr .
  682.    Calls        = Ident <
  683.       Call0     = .
  684.       Call      = '(' Actuals ')' .
  685.    > .
  686.    If           = IF Expr THEN Then: Stats ELSE Else: Stats 'END' .
  687. > .
  688. Expr            = <
  689.    Plus         = Lop: Expr '+' Rop: Expr .
  690.    Times        = Lop: Expr '*' Rop: Expr .
  691.    '()'         = '(' Expr ')' .
  692.    Adr          = <
  693.       Name      = Ident .
  694.       Index     = Adr '[' Expr ']' .
  695.    > .
  696. > .
  697. .)b
  698. .(b
  699. Example: output of cg -xz
  700. .sp 0.5
  701. .FT
  702. Stat : Adr ':=' Expr .
  703. Stat : Ident .
  704. Stat : Ident '(' Actuals ')' .
  705. Stat : IF Expr THEN Stats ELSE Stats 'END' .
  706.  
  707. Expr : Expr '+' Expr .
  708. Expr : Expr '*' Expr .
  709. Expr : '(' Expr ')' .
  710. Expr : Ident .
  711. Expr : Adr '[' Expr ']' .
  712.  
  713. Adr  : Ident .
  714. Adr  : Adr '[' Expr ']' .
  715. .)b
  716. The rule names and the selector names on the right-hand sides disappear (e. g. If). The
  717. extension formalism is expanded (e. g. Calls and Adr) \- it is not mapped to chain rules.
  718. The expansion includes the inheritance of children and attributes (e. g. Calls).
  719. All node types that are used somewhere become nonterminal symbols (e. g. Expr and Adr).
  720. .pp
  721. The rule names of non-referenced node types may be omitted. They are necessary for example
  722. if modules are used in order to refer from an attribute computation to a grammar rule.
  723. .(b
  724. Example without rule names:
  725. .sp 0.5
  726. .FT
  727. Stat  = -> [Tree: tTree] <
  728.       = Adr ':=' Expr         { Tree := mAssign (Adr:Tree, Expr:Tree);     } .
  729.       = Ident '(' Actuals ')' { Tree := mCall (Ident:Ident, Actuals:Tree); } .
  730. > .
  731. .sp 0.5
  732. Ident : [Ident: tIdent] .
  733. .)b
  734. .(b
  735. Example with rule names:
  736. .sp 0.5
  737. .FT
  738. Stat      = <
  739.    Assign = Adr ':=' Expr .
  740.    Call   = Ident '(' Actuals ')' .
  741. > .
  742. .sp 0.5
  743. Ident     : [Ident: tIdent] .
  744. .sp 0.5
  745. MODULE Tree
  746. .sp 0.5
  747. DECLARE Stat = -> [Tree: tTree] .
  748. .sp 0.5
  749. Assign    = { Tree := mAssign (Adr:Tree, Expr:Tree);         } .
  750. Call      = { Tree := mCall (Ident:Ident, Actuals:Tree);     } .
  751. .sp 0.5
  752. END Tree
  753. .)b
  754. .pp
  755. Attribute declarations and attribute computations are written exactly as for
  756. .i ast
  757. and
  758. .i ag .
  759. Attribute computations may be placed everywhere within right-hand sides, not only at the
  760. end. These computations are executed from left to right as parsing proceeds. They may only
  761. make use of those attributes that have already been computed before or to the left,
  762. respectively. The extension or inheritance mechanism for right-hand sides,
  763. attribute declarations, and attribute computations is available.
  764. The default computations (copy rules) for synthesized attributes are available, too. A
  765. specification may be separated into several modules. There could for example be modules for
  766. the concrete syntax, for the attribute declarations, and for the attribute computations. It
  767. is even possible to distribute the mentioned kinds of information into several modules.
  768. .pp
  769. Attribute declarations and attribute computations with named attributes replace the explicit
  770. declaration of the type
  771. .i tParsAttribute
  772. and the $i construct. The attribute declarations are transformed automatically into a
  773. declaration of the type
  774. .i tParsAttribute .
  775. The attribute computations in the new style are more readable and robust against changes. The
  776. given attribute computations are checked for completeness and whether the resulting attribute
  777. grammar obeys the SAG property. Only attribute grammars with synthesized attributes can be
  778. evaluated during parsing.
  779. .pp
  780. Every terminal has a predefined attribute named
  781. .i Position
  782. of type
  783. .i tPosition .
  784. This type is a user defined struct (record) type and has to contain at least the members
  785. .i Line
  786. and
  787. .i Column .
  788. This attribute describes the source coordinates of every token and it is computed
  789. automatically by
  790. .i rex
  791. generated scanners.
  792. The values of all other attributes of terminals have to be supplied by the scanner by
  793. user specified computations. Still, attribute computations for those attributes (except
  794. .i Position )
  795. have to be specified in the parser specification, too. They are used to generate the procedure
  796. .i ErrorAttribute .
  797. This procedure is called by the parser whenever tokens are inserted in order to repair syntax
  798. errors. The procedure and therefore the mentioned attribute computations have
  799. to supply default values for the attributes of tokens.
  800. .pp
  801. The right-hand side of a node type or a grammar rule, respectively, may contain actions
  802. to be executed during parsing. These actions may be placed at the end of the right-hand side
  803. or anywhere between the right-hand side elements. In any case these actions are executed from
  804. left to right according to the progress of parsing. The syntax of the actions is the one
  805. defined for the attribute computations of 
  806. .i ag .
  807. It is assumed that most of the actions will compute attributes.
  808. Actions which are not attribute computations are possible but
  809. have to be written as some kind of CHECK statement:
  810. .(b
  811. .FT
  812. => statement ;   or    => { statement_sequence } ;
  813. .)b
  814. .pp
  815. The following extensions of the language of
  816. .i ast
  817. and
  818. .i ag
  819. are used for parser generation, only.
  820. A grammar may be optionally headed by names for the modules to be generated:
  821. .(b
  822. .FT
  823. SCANNER Name PARSER Name
  824. .)b
  825. The first identifier specifies the module name of the scanner to be used by the parser.
  826. The second identifier specifies a name which is used to derive the names of the
  827. parsing module, the parsing routine, the parse tables, etc.
  828. If the names are missing they default to
  829. .i Scanner
  830. and
  831. .i Parser .
  832. In this document we refer to these names by <Scanner> and <Parser>.
  833. The parser name may be followed by a set of target code sections which
  834. is copied unchecked and unchanged to the input of the parser generator or the parser
  835. module, respectively:
  836. .(b
  837. .FT
  838. SCANNER Name
  839. PARSER  Name
  840. IMPORT { target_code }
  841. EXPORT { target_code }
  842. GLOBAL { target_code }
  843. LOCAL  { target_code }
  844. BEGIN  { target_code }
  845. CLOSE  { target_code }
  846. .)b
  847. .pp
  848. The precedence and associativity for operator tokens can be specified after the keyword PREC
  849. using LEFT, RIGHT, and NONE for left-, right-, and no associativity. Each group headed by one
  850. of the latter three keywords introduces a new group of tokens with increasing precedence.
  851. The precedence and associativity information is copied unchanged to the parser generator.
  852. .(b
  853. Example:
  854. .sp 0.5
  855. .FT
  856. PREC LEFT MONOP
  857.      NONE SEQ
  858.      LEFT '+' '-'
  859.      LEFT '*' '/' MOD
  860. .)b
  861. The precedence and associativity information is usually propagated implicitly to the grammar
  862. rules by taking it from the right-most token in a rule. Rules without an operator token
  863. can get the precedence and associativity from an operator token by adding a PREC clause
  864. at the end of a right-hand side.
  865. .(b
  866. Example:
  867. .sp 0.5
  868. .FT
  869. Expr = <
  870.      = Expr Expr PREC SEQ .   /* explicit  prec. + assoc. of SEQ          */
  871.      = '-'  Expr PREC MONOP . /* overwrite prec. + assoc. of '-' by MONOP */
  872.      = Expr '+' Expr .        /* implicit  prec. + assoc. of '+'          */
  873.      = Expr '-' Expr .        /* implicit  prec. + assoc. of '-'          */
  874. > .
  875. .)b
  876. .pp
  877. Tokens or terminal symbols are mapped automatically to integer numbers to be used as internal
  878. representation. This mapping can be overwritten by explicitly giving codes for terminals.
  879. .(b
  880. Example:
  881. .sp 0.5
  882. .FT
  883. Ident    :   [Ident: tIdent] .   /* implicitly coded      */
  884. IntConst : 5 [Value: int   ] .   /* explicitly coded as 5 */
  885. .)b
  886. .pp
  887. The attribute declarations for terminals are turned into a declaration of the type
  888. .i tScanAttribute .
  889. The scanner communicates attribute values of terminals to the parser using a global variable
  890. called
  891. .i Attribute
  892. which is of this type. This type is a union type (variant record) with one member (variant)
  893. for each terminal with attributes. The names of the terminals are taken for the names of
  894. these members (variants). However, this leads to problems if the terminals are named by
  895. strings or by keywords of the implementation language. Therefore terminals may have two
  896. names. The second one is used as member name in the type
  897. .i tScanAttribute .
  898. The predefined attribute
  899. .i Position
  900. mentioned above is always included in this type. Assignments of attribute values in the
  901. scanner therefore have to use two selections to describe an attribute:
  902. .(b
  903. .FT
  904. Attribute.<selector name>.<attribute name> = ...
  905. .)b
  906. .(b
  907. Example:
  908. .sp 0.5
  909. definition of terminals including attributes and member selectors in the parser specification
  910. .sp 0.5
  911. .FT
  912. Ident        : [Ident: tIdent] .   /* selector name: Ident   */
  913. \&':=' sAssign : [Ident: tIdent] .   /* selector name: sAssign */
  914. TRUE sTRUE   : [Ident: tIdent] .   /* selector name: sTRUE   */
  915. \&'..'         : [Ident: tIdent] .   /* selector name: yy17    */
  916. .)b
  917. .(b
  918. access of attributes in the scanner specification
  919. .sp 0.5
  920. .FT
  921. Attribute.Ident.Ident
  922. Attribute.sAssign.Ident
  923. Attribute.sTRUE.Ident
  924. Attribute.yy17.Ident
  925. .)b
  926. .(b
  927. access of attributes in the parser specification (at node directly)
  928. .sp 0.5
  929. .FT
  930. Ident                     Position
  931. .)b
  932. .(b
  933. access of attributes in the parser specification (from a child node)
  934. .sp 0.5
  935. .FT
  936. Ident:Ident               Ident:Position
  937. \&':=':Ident                ':=':Position
  938. TRUE:Ident                TRUE:Position
  939. \&'..':Ident                '..':Position
  940. .)b
  941. .pp
  942. The preprocessor for the parser specification is part of the program
  943. .i cg .
  944. It is called by the following command:
  945. .(b
  946. cg -xzvjc [ \fIParser\fP.pars ]
  947. .)b
  948. The input is read either from the file given as argument or from standard input if the
  949. argument is missing. The output is written to a file named <Parser>.lalr.
  950. The program is controlled by the following options:
  951. .(b
  952. .ta 1c
  953. x    generate scanner specification for rex
  954. z    generate parser  specification for lalr
  955. v    omit actions in the generated parser specification
  956. j    allow undefined node types; define implicitly as terminals
  957. c    generate C source code (default is Modula-2)
  958. .)b
  959. .pp
  960. Appendix 1 of the
  961. .i ag
  962. manual\*([<\*([[Gro89\*(]]\*(>] contains the complete formal syntax understood by the program
  963. .i cg .
  964. Appendix 2 of this manual shows a parser specification for the example language MiniLAX.
  965. It separates context-free grammar and attribute computations in two modules.
  966. The attribute computations in the module
  967. .i Tree
  968. use one attribute also called
  969. .i Tree
  970. and describe the construction of an abstract syntax tree by calling functions generated by
  971. .i ast .
  972. The implementation language is C.
  973. .sh 2 "Scanner Specification"
  974. .pp
  975. The scanner specification has to contain only those parts that can not be extracted
  976. automatically from the parser specification. This is as already mentioned above
  977. the description of user-defined tokens like identifiers and numbers, comments, and the
  978. computation of attributes for the tokens. The formalism to describe this fragmentary
  979. scanner specification (.scan) is the input language of rex\*([<\*([[Gro87\*(]]\*(>].
  980. It may contain three insertion points which instruct the preprocessor
  981. .i rpp
  982. (rex preprocessor) to include certain generated parts. Moreover, tokens in return statements
  983. can be denoted by the same strings or identifiers as in the parser specification.
  984. .lp
  985. .(b
  986. .FT
  987. INSERT tScanAttribute
  988. .)b
  989. in the EXPORT section is replaced by the generated declaration of the type
  990. .i tScanAttribute
  991. and the head or external declaration of the procedure
  992. .i ErrorAttribute .
  993. .(b
  994. .FT
  995. INSERT ErrorAttribute
  996. .)b
  997. in the GLOBAL section is replaced by the body of the generated procedure
  998. .i ErrorAttribute .
  999. .pp
  1000. The third insertion point lies in the RULE section and has the following syntax
  1001. (only the brackets
  1002. .FT
  1003. [ ]
  1004. .FR
  1005. are used as meta characters and denote optional parts):
  1006. .(b
  1007. .FT
  1008. INSERT RULES [CASE-INSENSITIVE] [[NOT] #<start_states>#] [{ <target_code> }]
  1009. .)b
  1010. It is replaced by as many rules as there are tokens extracted automatically from the
  1011. parser specification. Every rule has the following format:
  1012. .(b
  1013. .FT
  1014. NOT # <start_states> # <token> : { <target_code> return <code>; }
  1015. .)b
  1016. The start states including the keyword NOT and the target code are optional and are copied to
  1017. the generated rule as indicated. If CASE-INSENSITIVE is specified, the regular expressions
  1018. for the tokens are constructed to match lower as well as upper case letters.
  1019. Note, only rules for tokens without explicitly declared attributes are constructed
  1020. automatically.
  1021. .pp
  1022. Within a rule, return (or RETURN) statements are used to report the internal code of a
  1023. recognized token. The expression of those statements can be any expression of the
  1024. implementation language or a string or an identifier used in the parser specification.
  1025. The latter are replaced by their internal representation.
  1026. .(b
  1027. Example:
  1028. .sp 0.5
  1029. .FT
  1030. return 5;
  1031. return Ident;
  1032. return ':=';
  1033. .)b
  1034. .pp
  1035. The program
  1036. .i rpp
  1037. is called by the following command:
  1038. .(b
  1039. rpp [ \fIScanner\fP.rpp ] < \fIScanner\fP.scan > \fIScanner\fP.rex
  1040. .)b
  1041. The fragmentary scanner specification is read from standard input.
  1042. The scanner specification extracted from the parser specification is read from a file
  1043. given as argument. This argument is optional and defaults to
  1044. .i Scanner.rpp .
  1045. The scanner specification understood by \fIrex\fP is written on standard output.
  1046. The basename \fIScanner\fP in the command line above is usually substituted by the name of
  1047. the scanner module.
  1048. .pp
  1049. Appendix 1 contains a scanner specification for the example language MiniLAX.
  1050. It uses C as implementation language.
  1051. .(b L
  1052. .sp 0.5
  1053. .PS
  1054. scale    = 2.54
  1055. boxwid    = 2.0
  1056. boxht    = 1.2
  1057. circlerad = 0.6
  1058. linewid    = 1.2
  1059. lineht    = 1.2
  1060. movewid    = 1.2
  1061. moveht    = 1.2
  1062.  
  1063.     down
  1064. Y:    box ".yacc"
  1065.     arrow
  1066. Y2:    circle "y2l"
  1067.     arrow
  1068. La:    box ".lalr"
  1069.     arrow
  1070.     circle "lalr"
  1071.     arrow
  1072.  
  1073.     left
  1074. P:    box ".pars" at Y.e + (4.6, 0)
  1075.     arrow
  1076.     circle "cg -u"
  1077.     arrow to Y.e
  1078.  
  1079.     left
  1080. E:    box ".ell" at La.e + (4.6, 0)
  1081.     arrow
  1082.     circle "bnf"
  1083.     arrow to La.e
  1084.  
  1085.     arrow at E.s down
  1086.     circle "ell"
  1087.     arrow
  1088.  
  1089. Z:    circle "cg -z" at Y2 + (2.8, 0)
  1090.     arrow from P.sw to Z.ne
  1091.     arrow from Z.sw to La.ne
  1092.  
  1093. Le:    box ".lex" at Y.w - (6.6, 0)
  1094.     move down
  1095. D0:    box invis width 3.0
  1096.     move down
  1097. R:    box ".rex"
  1098.     arrow
  1099.     circle "rex"
  1100.     arrow
  1101.  
  1102. L2:    circle "l2r" at D0.w
  1103. R2:    circle "r2l" at D0.e
  1104.     arrow from Le.s to L2.n
  1105.     arrow from L2.s to R.n
  1106.     arrow from R.n to R2.s
  1107.     arrow from R2.n to Le.s
  1108.  
  1109.     arrow at R.e + (3.6, 0) left
  1110.     circle "rpp"
  1111.     arrow to R.e
  1112. .PE
  1113. .sp
  1114. .ce
  1115. Fig. 2: Conversion programs for scanner and parser specifications
  1116. .)b
  1117. .sh 1 "Conversion of Scanner and Parser Specifications"
  1118. .sh 2 "Input Languages"
  1119. .pp
  1120. The input languages of
  1121. .i rex
  1122. and
  1123. .i lalr
  1124. have been designed to be as readable as possible. Although they contain the same information
  1125. as inputs for
  1126. .i lex
  1127. \*([[Les75\*(]] and
  1128. .i yacc
  1129. \*([[Joh75\*(]] they are syntactically incompatible. Several conversion programs allow the
  1130. transformation of input for
  1131. .i rex
  1132. and
  1133. .i lalr
  1134. to input for
  1135. .i lex
  1136. and
  1137. .i yacc
  1138. or vice versa.
  1139. Fig.2 shows the possible conversions for scanner and parser specifications.
  1140. Table 2 lists the existing filter programs and the types of their input and
  1141. output files.
  1142. .(z L
  1143. .sp 0.5
  1144. .ce
  1145. Table 2: Filters for input conversion
  1146. .sp 0.5
  1147. .TS
  1148. center box;
  1149. l | l | l.
  1150. filter    input    output
  1151. _
  1152. l2r    .lex    .rex
  1153. r2l    .rex    .lex
  1154. y2l    .yacc    .lalr
  1155. cg -u    .pars    .yacc
  1156. cg -z    .pars    .lalr
  1157. bnf    .ell    .lalr
  1158. .TE
  1159. .)z
  1160. .pp
  1161. The option '-v' instructs
  1162. .i y2l
  1163. and
  1164. .i cg
  1165. to omit the semantic actions in the produced output.
  1166. The following restrictions or problems are known to exist because they can not be mapped to
  1167. the target tool:
  1168. .br
  1169. .ne 2c
  1170. .lp
  1171. .i l2r
  1172. .ta 2.5c
  1173. .ip -
  1174. yymore
  1175. .ip -
  1176. REJECT
  1177. .ip -
  1178. yywrap    (redirection can be done with \fIrex\fP, but differently)
  1179. .ip -
  1180. %T    (specification of the character set is not possible)
  1181. .br
  1182. .ne 2c
  1183. .lp
  1184. .i r2l
  1185. .ip -
  1186. yyPrevious
  1187. .ip -
  1188. EOF    (specifies actions to be performed upon reaching end of file)
  1189. .br
  1190. .ne 2c
  1191. .lp
  1192. .i y2l
  1193. .ip -
  1194. The conversion of token definitions may not be completely automatic.
  1195. .ip -
  1196. If scanning depends on information collected by the parser then parsers generated by
  1197. .i yacc
  1198. and
  1199. .i lalr
  1200. may behave differently because they do not agree upon the order or timing, respectively,
  1201. of the execution of read (shift) and reduce actions.
  1202. .br
  1203. .ne 2c
  1204. .lp
  1205. .i bnf
  1206. .ip -
  1207. The attribute computations for
  1208. .i ell
  1209. and
  1210. .i lalr
  1211. are different and are not converted.
  1212. .sh 2 "Interfaces"
  1213. .pp
  1214. The interfaces of scanners and parsers generated by
  1215. .i lex/yacc
  1216. and
  1217. .i rex/lalr
  1218. are incompatible. The differences are primarily caused by different names for the
  1219. external (exported) objects. Table 3 lists the interface objects.
  1220. .(z L
  1221. .sp 0.5
  1222. .ce
  1223. Table 3: Interfaces of generated scanners and parsers
  1224. .sp 0.5
  1225. .TS
  1226. center box;
  1227. l | l | l.
  1228. object    yacc/lex    lalr/rex
  1229. _
  1230. parse routine    int yyparse ();    int Parser ();
  1231. stack size    YYMAXDEPTH    yyInitStackSize
  1232. attribute type    YYSTYPE    tParsAttribute
  1233. _
  1234. global attribute    YYSTYPE yylval;    tScanAttribute Attribute;
  1235. _
  1236. position type         typedef struct { short Line, Column; ... } tPosition;
  1237. attribute type         typedef struct { tPosition Position; ... } tScanAttribute;
  1238. scanner routine    int yylex ();    int GetToken ();
  1239. error repair         void ErrorAttribute ();
  1240. line number    int yylineno;    \fImember\fP Attribute.Position.Line
  1241. token buffer    char yytext [];
  1242. token length    int yyleng;
  1243. .TE
  1244. .)z
  1245. The interfaces of the scanners and parsers generated by
  1246. .i rex
  1247. and
  1248. .i lalr
  1249. can be switched from the default as listed in Table 3 to an approximation of the
  1250. .i lex
  1251. and
  1252. .i yacc
  1253. interfaces. This is controlled by
  1254. .i cpp
  1255. commands:
  1256. .(b
  1257. .FT
  1258. # define lex_interface
  1259. .)b
  1260. in the EXPORT section of a
  1261. .i rex
  1262. specification selects a lex-style interface for the scanner.
  1263. .(b
  1264. .FT
  1265. # define lex_interface
  1266. .)b
  1267. in the EXPORT section of a
  1268. .i lalr
  1269. specification tells the parser to use a lex-style interface for the scanner.
  1270. .(b
  1271. .FT
  1272. # define yacc_interface
  1273. .)b
  1274. in the EXPORT section of a
  1275. .i lalr
  1276. specification selects a yacc-style interface for the parser.
  1277. .pp
  1278. The output of the preprocessors
  1279. .i l2r
  1280. and
  1281. .i y2l
  1282. automatically selects lex- and yacc-style interfaces. The following problems
  1283. are known, currently:
  1284. .ip -
  1285. The output of
  1286. .i l2r
  1287. provides the matched string in the array
  1288. .i yytext
  1289. to be used in action statements. This is done by calling the procedure
  1290. .i Getword .
  1291. However, many actions do not need
  1292. .i yytext .
  1293. Deleting superfluous calls of
  1294. .i Getword
  1295. will make the scanner significantly faster.
  1296. .ip -
  1297. Access to the line counter
  1298. .i yylineno
  1299. has to be replaced by access to
  1300. .(b
  1301. .FT
  1302. Attribute.Position.Line
  1303. .)b
  1304. .ip -
  1305. If both, scanner and parser specification have been converted by
  1306. .i l2r
  1307. and
  1308. .i y2l
  1309. in order to be fed into
  1310. .i rex
  1311. and
  1312. .i lalr ,
  1313. the two preprocessor statements which define
  1314. .i lex_interface
  1315. should be deleted in order to select the standard interface. This offers more comfort with
  1316. respect to the information about the source position.
  1317. .lp
  1318. .sp
  1319. .b Acknowledgements
  1320. .pp
  1321. The preprocessor
  1322. .i bnf
  1323. has been implemented by Bertram Vielsack. The preprocessors
  1324. .i y2l ,
  1325. .i l2r ,
  1326. .i rpp ,
  1327. and
  1328. .i "cg -xz"
  1329. have been implemented by Thomas M\*uller.
  1330. .fi
  1331. .sz 12
  1332. .[]
  1333. .[-
  1334. .ds [F Gro87
  1335. .ds [A J\*(p] Grosch
  1336. .ds [T Rex - A Scanner Generator
  1337. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1338. .ds [R Compiler Generation Report No. 5
  1339. .ds [N 5
  1340. .ds [D Dec. 1987
  1341. .][
  1342. .[-
  1343. .ds [F GrV88
  1344. .ds [A J\*(p] Grosch
  1345. .as [A \*(n]B\*(p] Vielsack
  1346. .ds [T The Parser Generators Lalr and Ell
  1347. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1348. .ds [R Compiler Generation Report No. 8
  1349. .ds [N 8
  1350. .ds [D Apr. 1988
  1351. .][
  1352. .[-
  1353. .ds [F Gro89
  1354. .ds [A J\*(p] Grosch
  1355. .ds [T Ag - An Attribute Evaluator Generator
  1356. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1357. .ds [R Compiler Generation Report No. 16
  1358. .ds [N 16
  1359. .ds [D Aug. 1989
  1360. .][
  1361. .[-
  1362. .ds [F Gro91
  1363. .ds [A J\*(p] Grosch
  1364. .ds [T Ast - A Generator for Abstract Syntax Trees
  1365. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1366. .ds [R Compiler Generation Report No. 15
  1367. .ds [N 15
  1368. .ds [D Sep. 1991
  1369. .][
  1370. .[-
  1371. .ds [F Joh75
  1372. .ds [A S\*(p]\*(a]C\*(p] Johnson
  1373. .ds [T Yacc \(em  Yet Another Compiler-Compiler
  1374. .ds [R Computer Science Technical Report 32
  1375. .ds [I Bell Telephone Laboratories
  1376. .ds [C Murray Hill, NJ
  1377. .ds [D July 1975
  1378. .][
  1379. .[-
  1380. .ds [F Les75
  1381. .ds [A M\*(p]\*(a]E\*(p] Lesk
  1382. .ds [T LEX \(em A Lexical Analyzer Generator
  1383. .ds [R Computing Science Technical Report 39
  1384. .ds [I Bell Telephone Laboratories
  1385. .ds [C Murray Hill, NJ
  1386. .ds [D 1975
  1387. .][
  1388. .bp
  1389. .uh "Appendix 1: Scanner Specification for MiniLAX"
  1390. .sp
  1391. .nf
  1392. .FT
  1393. EXPORT  {
  1394. # include "Idents.h"
  1395. # include "Positions.h"
  1396. .sp 0.5
  1397. INSERT tScanAttribute
  1398. }
  1399. .sp 0.5
  1400. GLOBAL  {
  1401. # include <math.h>
  1402. # include "Memory.h"
  1403. # include "StringMem.h"
  1404. # include "Idents.h"
  1405. # include "Errors.h"
  1406. .sp 0.5
  1407. INSERT ErrorAttribute
  1408. }
  1409. .sp 0.5
  1410. LOCAL   { char Word [256]; }
  1411. .sp 0.5
  1412. DEFAULT {
  1413. MessageI ("illegal character", xxError, Attribute.Position, xxCharacter, TokenPtr);
  1414. }
  1415. .sp 0.5
  1416. EOF     {
  1417.    if (yyStartState == Comment)
  1418.       Message ("unclosed comment", xxError, Attribute.Position);
  1419. }
  1420. .sp 0.5
  1421. DEFINE  digit   = {0-9} .
  1422.         letter  = {a-z A-Z} .
  1423. .sp 0.5
  1424. START   Comment
  1425. .sp 0.5
  1426. RULE
  1427.           "(*"  :- {yyStart (Comment);}
  1428. #Comment# "*)"  :- {yyStart (STD);}
  1429. #Comment# "*" | - {*\\t\\n} + :- {}
  1430. .sp 0.5
  1431. #STD# digit +   : {(void) GetWord (Word);
  1432.                    Attribute.IntegerConst.Integer = atoi (Word);
  1433.                    return IntegerConst;}
  1434. .sp 0.5
  1435. #STD# digit * "." digit + (E {+\\-} ? digit +) ?
  1436.                 : {(void) GetWord (Word);
  1437.                    Attribute.RealConst.Real = atof ((char *) Word);
  1438.                    return RealConst;}
  1439. .sp 0.5
  1440. INSERT RULES #STD#
  1441. .sp 0.5
  1442. #STD# letter (letter | digit) *
  1443.                 : {Attribute.Ident.Ident = MakeIdent (TokenPtr, TokenLength);
  1444.                    return Ident;}
  1445. .bp
  1446. .uh "Appendix 2: Parser Specification for MiniLAX"
  1447. .sp
  1448. .nf
  1449. .FT
  1450. PARSER
  1451.  
  1452. GLOBAL {# include "Idents.h" }
  1453.  
  1454. BEGIN  { BeginScanner (); }
  1455.  
  1456. PREC    LEFT    '<'                             /* operator precedence  */
  1457.         LEFT    '+'
  1458.         LEFT    '*'
  1459.         LEFT    NOT
  1460.  
  1461. PROPERTY INPUT
  1462.  
  1463. RULE                                            /* concrete syntax      */
  1464.  
  1465. Prog            = PROGRAM Ident ';' 'DECLARE' Decls 'BEGIN' Stats 'END' '.' .
  1466. Decls           = <
  1467.    Decls1       = Decl .
  1468.    Decls2       = Decls ';' Decl .
  1469. > .
  1470. Decl            = <
  1471.    Var          = Ident ':' Type .
  1472.    Proc0        = PROCEDURE Ident ';' 'DECLARE' Decls 'BEGIN' Stats 'END' .
  1473.    Proc         = PROCEDURE Ident '(' Formals ')' ';'
  1474.                                       'DECLARE' Decls 'BEGIN' Stats 'END' .
  1475. > .
  1476. Formals         = <
  1477.    Formals1     = Formal .
  1478.    Formals2     = Formals ';' Formal .
  1479. > .
  1480. Formal          = <
  1481.    Value        = Ident ':' Type .
  1482.    Ref          = VAR Ident ':' Type .
  1483. > .
  1484. Type            = <
  1485.    Int          = INTEGER .
  1486.    Real         = REAL .
  1487.    Bool         = BOOLEAN .
  1488.    Array        = ARRAY '[' Lwb: IntegerConst '..' Upb: IntegerConst ']' OF Type .
  1489. > .
  1490. Stats           = <
  1491.    Stats1       = Stat .
  1492.    Stats2       = Stats ';' Stat .
  1493. > .
  1494. Stat            = <
  1495.    Assign       = Adr ':=' Expr .
  1496.    Call0        = Ident .
  1497.    Call         = Ident '(' Actuals ')' .
  1498.    If           = IF Expr THEN Then: Stats ELSE Else: Stats 'END' .
  1499.    While        = WHILE Expr DO Stats 'END' .
  1500.    Read         = READ '(' Adr ')' .
  1501.    Write        = WRITE '(' Expr ')' .
  1502. > .
  1503. Actuals         = <
  1504.    Expr1        = Expr .
  1505.    Expr2        = Actuals ',' Expr .
  1506. > .
  1507. .bp
  1508. Expr            = <
  1509.    Less         = Lop: Expr '<' Rop: Expr .
  1510.    Plus         = Lop: Expr '+' Rop: Expr .
  1511.    Times        = Lop: Expr '*' Rop: Expr .
  1512.    Not          = NOT Expr .
  1513.    '()'         = '(' Expr ')' .
  1514.    IConst       = IntegerConst .
  1515.    RConst       = RealConst .
  1516.    False        = FALSE .
  1517.    True         = TRUE .
  1518.    Adr          = <
  1519.       Name      = Ident .
  1520.       Index     = Adr '[' Expr ']' .
  1521.    > .
  1522. > .
  1523.  
  1524.                                         /* terminals (with attributes)  */
  1525.  
  1526. Ident           : [Ident: tIdent] { Ident       := NoIdent      ; } .
  1527. IntegerConst    : [Integer      ] { Integer     := 0            ; } .
  1528. RealConst       : [Real : float ] { Real        := 0.0          ; } .
  1529.  
  1530. MODULE Tree
  1531.                         /* import functions for tree construction       */
  1532. PARSER GLOBAL   {
  1533. # include "Tree.h"
  1534.  
  1535. tTree  nInteger, nReal, nBoolean;
  1536. }
  1537.  
  1538. BEGIN   {
  1539.    nInteger     = mInteger      ();
  1540.    nReal        = mReal         ();
  1541.    nBoolean     = mBoolean      ();
  1542. }
  1543. .bp
  1544.                         /* attributes for tree construction             */
  1545. DECLARE
  1546.   Decls Decl Formals Formal Type Stats Stat Actuals Expr = [Tree: tTree] .
  1547.  
  1548. RULE                    /* tree construction =                          */
  1549.                         /* mapping: concrete syntax -> abstract syntax  */
  1550.  
  1551. Prog    = { => { TreeRoot = mMiniLax (mProc (mNoDecl (), Ident:Ident,
  1552.                  Ident:Position, mNoFormal (), ReverseTree (Decls:Tree),
  1553.                  ReverseTree (Stats:Tree)));};                                  } .
  1554. Decls1  = { Tree := {Decl:Tree->\\Decl.Next = mNoDecl (); Tree = Decl:Tree;};    } .
  1555. Decls2  = { Tree := {Decl:Tree->\\Decl.Next = Decls:Tree; Tree = Decl:Tree;};    } .
  1556. Var     = { Tree := mVar (NoTree, Ident:Ident, Ident:Position, mRef (Type:Tree));}.
  1557. Proc0   = { Tree := mProc (NoTree, Ident:Ident, Ident:Position, mNoFormal (),
  1558.                     ReverseTree (Decls:Tree), ReverseTree (Stats:Tree));        } .
  1559. Proc    = { Tree := mProc (NoTree, Ident:Ident, Ident:Position, ReverseTree
  1560.            (Formals:Tree), ReverseTree (Decls:Tree), ReverseTree (Stats:Tree)); } .
  1561. Formals1= { Tree := {Formal:Tree->\\Formal.Next = mNoFormal ();
  1562.                     Tree = Formal:Tree;};                                       } .
  1563. Formals2= { Tree := {Formal:Tree->\\Formal.Next = Formals:Tree;
  1564.                     Tree = Formal:Tree;};                                       } .
  1565. Value   = { Tree := mFormal (NoTree, Ident:Ident, Ident:Position,
  1566.                     mRef (Type:Tree));                                          } .
  1567. Ref     = { Tree := mFormal (NoTree, Ident:Ident, Ident:Position,
  1568.                     mRef (mRef (Type:Tree)));                                   } .
  1569. Int     = { Tree := nInteger;                                                   } .
  1570. Real    = { Tree := nReal;                                                      } .
  1571. Bool    = { Tree := nBoolean;                                                   } .
  1572. Array   = { Tree := mArray (Type:Tree, Lwb:Integer, Upb:Integer, Lwb:Position); } .
  1573. Stats1  = { Tree := {Stat:Tree->\\Stat.Next = mNoStat (); Tree = Stat:Tree;};    } .
  1574. Stats2  = { Tree := {Stat:Tree->\\Stat.Next = Stats:Tree; Tree = Stat:Tree;};    } .
  1575. Assign  = { Tree := mAssign (NoTree, Adr:Tree, Expr:Tree, ':=':Position);       } .
  1576. Call0   = { Tree := mCall (NoTree, mNoActual (Ident:Position), Ident:Ident,
  1577.                     Ident:Position);                                            } .
  1578. Call    = { Tree := mCall (NoTree, ReverseTree (Actuals:Tree), Ident:Ident,
  1579.                     Ident:Position);                                            } .
  1580. If      = { Tree := mIf (NoTree, Expr:Tree, ReverseTree (Then:Tree),
  1581.                     ReverseTree (Else:Tree));                                   } .
  1582. While   = { Tree := mWhile (NoTree, Expr:Tree, ReverseTree (Stats:Tree));       } .
  1583. Read    = { Tree := mRead (NoTree, Adr:Tree);                                   } .
  1584. Write   = { Tree := mWrite (NoTree, Expr:Tree);                                 } .
  1585. Expr1   = { Tree := mActual (mNoActual (Expr:Tree->\\Expr.Pos), Expr:Tree);      } .
  1586. Expr2   = { Tree := mActual (Actuals:Tree, Expr:Tree);                          } .
  1587. Less    = { Tree := mBinary ('<':Position, Lop:Tree, Rop:Tree, Less);           } .
  1588. Plus    = { Tree := mBinary ('+':Position, Lop:Tree, Rop:Tree, Plus);           } .
  1589. Times   = { Tree := mBinary ('*':Position, Lop:Tree, Rop:Tree, Times);          } .
  1590. Not     = { Tree := mUnary (NOT:Position, Expr:Tree, Not);                      } .
  1591. IConst  = { Tree := mIntConst (IntegerConst:Position, IntegerConst:Integer);    } .
  1592. RConst  = { Tree := mRealConst (RealConst:Position, RealConst:Real);            } .
  1593. False   = { Tree := mBoolConst (FALSE:Position, false);                         } .
  1594. True    = { Tree := mBoolConst (TRUE:Position, true);                           } .
  1595. Name    = { Tree := mIdent (Ident:Position, Ident:Ident);                       } .
  1596. Index   = { Tree := mIndex ('[':Position, Adr:Tree, Expr:Tree);                 } .
  1597.  
  1598. END Tree
  1599. .bp 1
  1600. .lp
  1601. .b Contents
  1602. .sp
  1603. .xp
  1604.